#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 034. 在排序数组中查找元素的第一个和最后一个位置.py
@time: 2022/1/28 16:54
@desc: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
> 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

1. Ot(logN), Os(1)

'''
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums: return [-1, -1]
        n = len(nums)
        ans = []
        def bs(lt, rt):
            if lt<=rt:
                mid = (lt+rt)//2
                if nums[mid]==target:
                    bs(lt, mid-1)
                    ans.append(mid)
                    bs(mid+1, rt)
                elif target<nums[mid]:
                    bs(lt, mid-1)
                else:
                    bs(mid+1, rt)
        bs(0, n-1)
        if not ans: return [-1, -1]
        return [ans[0], ans[-1]]

class Solution02:
    def searchRange(self, nums, target):
        def findFirst(nums, target):
            left, right = 0, len(nums)-1
            while left<right:
                # 向下取整
                mid = left + (right-left)//2
                if nums[mid]<target:
                    left = mid + 1
                else:
                    right = mid
            # 检查是否是答案
            if nums[left]==target: return left
            return -1
        def findLast(nums, target):
            left, right = 0, len(nums)-1
            while left<right:
                # 向上取整
                mid = left + (right-left+1)//2
                if nums[mid]>target:
                    right = mid-1
                else:
                    left=mid
            return left
        n = len(nums)
        if n==0: return [-1, -1]
        first = findFirst(nums, target)
        if first==-1: return [-1, -1]
        last = findLast(nums, target)
        return [first, last]

if __name__ == '__main__':
    nums = [5,7,7,8,8,10]
    target = 8
    res = Solution02().searchRange(nums, target)
    print(res)
